package com.copa.l264;

import java.util.*;

/**
 * @author copa
 * @createDate 2022-05-31 16:59
 * @function 最小堆法
 */
public class Test1 {

    public int nthUglyNumber(int n) {
        // 定义小根堆，可以利用排出最小数的特性来返回结果
        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
        // 先加1
        priorityQueue.add(1L);
        // 这个只是用作去重与判断的作用
        Set<Long> set = new HashSet<>();
        // 先加1
        set.add(1L);
        // 返回结果
        int result = 1;
        // 定义这个是因为可能这个丑数会非常大，int都不够装的
        long pivotLong;
        // 这个对比下面来说就是简洁写法了，不然就*2 *3 *5这样
        long[] factors = {2L, 3L, 5L};
        for (int i = 0; i < n; i++) {
            // 输入n就要遍历n次
            pivotLong = priorityQueue.poll();
            // 因为题目要求用int返回结果，所以这步必须要走
            result = (int) pivotLong;
            for (long factor : factors) {
                // 这个对比下面来说是优化版写法了
                long newNum = factor * pivotLong;
                if (!set.contains(newNum)) {
                    set.add(newNum);
                    priorityQueue.add(newNum);
                }
            }
        }
        return result;
    }

//    public int nthUglyNumber(int n) {
//        // 定义小根堆，可以利用排出最小数的特性来返回结果
//        PriorityQueue<Long> priorityQueue = new PriorityQueue<>();
//        // 先加1
//        priorityQueue.add(1L);
//        // 这个只是用作去重与判断的作用
//        Set<Long> set = new TreeSet<>();
//        set.add(1L);
//        // 返回结果
//        int pivot = 1;
//        // 定义这个是因为可能这个丑数会非常大，int都不够装的
//        long pivotLong = 1;
//        int i = 0;
//        while (i < n) {
//            // 输入n就要遍历n次
//            pivotLong = priorityQueue.poll();
//            pivot = (int) pivotLong;
//            // 丑数是按照 *2 *3 *5 来进行的，但我也觉得这样写有些不妥...还是看看上面的简洁写法吧
//            if (!set.contains(pivotLong * 2)) {
//                priorityQueue.add(Long.valueOf(pivotLong * 2));
//                set.add(Long.valueOf(pivotLong * 2));
//            }
//            if (!set.contains(pivotLong * 3)) {
//                priorityQueue.add(Long.valueOf(pivotLong * 3));
//                set.add(Long.valueOf(pivotLong * 3));
//            }
//            if (!set.contains(pivotLong * 5)) {
//                priorityQueue.add(Long.valueOf(pivotLong * 5));
//                set.add(Long.valueOf(pivotLong * 5));
//            }
//            i++;
//        }
//        return pivot;
//    }

    public static void main(String[] args) {
        System.out.println(new Test1().nthUglyNumber(10));
    }
}
